//
// Created by PC on 2024/7/17.
/*
 讲解视频:https://www.bilibili.com/video/BV1DW4y1m7rE/?spm_id_from=333.337.search-card.all.click&vd_source=f69fe937b6744667b35fadd0fa06ddd2*
 讲解:http://t.csdnimg.cn/WqZxv
 *一本通 P233 例4.5 集合的划分
OJ:http://ybt.ssoier.cn:8088/problem_show.php?pid=1315 PASS
时间限制: 1000 ms         内存限制: 65536 KB
提交数:31109    通过数: 15835
【题目描述】

设S是一个具有n个元素的集合，S＝〈a1，a2，……，an〉，现将S划分成k个满足下列条件的子集合S1，S2，……，Sk ，且满足：
1．Si≠∅𝑆𝑖≠∅
2．Si∩Sj＝∅          (1≤i，j≤k，i≠j)
3．S1∪S2∪S3∪…∪Sk＝S
则称S1，S2，……，Sk，……，𝑆𝑘是集合S的一个划分。它相当于把S集合中的n个元素a1，a2，……，an 放入k𝑘个(0＜k≤n＜30)无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1，a2，……，an放入k个无标号盒子中去的划分数S(n,k)。
【输入】
给出n和k。
【输出】
n个元素a1，a2，……，an放入k个无标号盒子中去的划分数S(n,k)。
【输入样例】
10 6
【输出样例】
22827
 * */
//


#include <iostream>

using namespace std;

// 用int可能会溢出
long long sets(int n, int k)
{
    if (n<k || k==0)
        return 0;
    else if (n==k || k==1)
        return 1;
    return sets(n-1,k-1) + k*sets(n-1,k);
}

int main()
{
    int n=10,k=6;
//    cin>>n>>k;
    cout<<sets(n,k);
    return 0;
}